package com.guaoran.algorithm.node.list;

import com.guaoran.algorithm.common.CommonUtil;
import com.guaoran.algorithm.entity.Node;

/**
 * @Desc： 翻转链表
 * @Auth gucheng
 * @Date 2020/12/16 上午11:31
 */
public class ReverseNodeList {

    public static void main(String[] args) {
        Node head = CommonUtil.createNode(6);
        System.out.println(head);
        Node<Integer> reverse = reverse(head);
        System.out.println(reverse);
        head = CommonUtil.createNode(6);
        Node<Integer> reverseBetween = reverseBetween(head,2,6);
        System.out.println(reverseBetween);
    }

    /**
     * 翻转链表
     * @param head
     *  https://leetcode.com/submissions/detail/431543878/
     * @return
     */
    public static Node<Integer> reverse(Node<Integer> head){
        if(head == null)
            return null;
        Node pre = head;
        Node current = head.next;
        pre.next = null;
        while(current!=null){
            Node next = current.next;
            current.next = pre;
            pre = current;
            current = next;
        }
        return pre;
    }

    /**
     * 翻转链表在 m 和 n 之间的节点
     * @param head
     * @param m
     * @param n
     * https://leetcode.com/submissions/detail/431500143/
     * @return
     */
    public static Node<Integer> reverseBetween(Node<Integer> head ,int m ,int n){
        if(head == null || m>=n) return head;
        // 哨兵
        Node<Integer> dummy = new Node<>(-1);
        dummy.next = head;
        head = dummy;

        for (int i = 1; i < m; i++) {
            head = head.next;
        }
        Node<Integer> preM = head; // m 的前一个元素
        Node<Integer> mNode = head.next;// m 下标的元素
        Node<Integer> nNode = mNode;
        Node<Integer> postN = nNode.next;// n 下标元素的后一个元素
        // 翻转 m 和 n 之间的元素
        for (int i = m; i <n; i++) {
            Node<Integer> next = postN.next;
            postN.next =  nNode;
            nNode = postN;
            postN = next;
        }
        mNode.next = postN;
        preM.next = nNode;
        return dummy.next;
    }

}
